package com.itheima.algorithm.twothreetree;

import java.util.Arrays;

public class BTree {

    static class Node{
        int[] keys;//关键字
        Node[] children;//孩子
        int keyNumber;//有效关键字数目
        boolean leaf=true;//是否是叶子节点
        int t;//最小度数（最小孩子数）

        public Node(int t){ //t>=2
            this.t=t;
            this.children=new Node[2*t];  //孩子数目 ceil（m/2)~m
            this.keys=new int[2*t-1];     //关键字数目  ceil（m/2)~m-1
        }

        @Override
        public String toString(){
            return Arrays.toString(Arrays.copyOfRange(keys,0,keyNumber));
        }

        //多路查找
        Node get(int key){
            int i=0;
            while(i<keyNumber){
                if(keys[i]==key){
                    return this;
                }
                if(keys[i]>key){
                    break;
                }
                i++;
            }
            //这里是是keys【i】>key或者是i==keyNumber
            //叶子节点
            if(leaf){
                return null;
            }
            //非叶子节点就去孩子里面找
            return children[i].get(key);
        }

        //向keys指定索引处index插入元素
        void insertKey(int key,int index){
            System.arraycopy(keys,index,keys,index+1,keyNumber-index);
            keys[index]=key;
            keyNumber++;
        }

        //向children指定索引处插入child
        void insertChild(Node child,int index){
            System.arraycopy(children,index,children,index+1,keyNumber-index);
            children[index]=child;
        }
    }

    Node root;

    int t;//树中节点的最小度数
    final int MIN_KEY_NUMBER;//最小key数量
    final int MAX_KEY_NUMBER;//最大key数量

    public BTree(){
        this(2);
    }

    public BTree(int t){
        this.t=t;
        root=new Node(t);
        MAX_KEY_NUMBER=2*t-1;
        MIN_KEY_NUMBER=t-1;
    }

    //查找key是否存在
    public boolean contains(int key){
        return root.get(key)!=null;
    }

    //新增操作
    public void put(int key){
        doPut(root,key);
    }

    private void doPut(Node node,int key){
        int i=0;
        while(i<node.keyNumber){
            if(node.keys[i]==key){
                return;//key已经存在，无需操作
            }
            if(node.keys[i]>key){
                break;//代表找到了插入位置
            }
            i++;
        }
        //叶子节点就直接插入
        if(node.leaf){
            node.insertKey(key,i);
        }else{
            doPut(node.children[i],key);
        }
    }

    private void split(Node left,Node parent,int inxdex){
        //4.如果分裂的是根节点
        if(parent==null){
            //那就创建一个新节点
            Node newRoot=new Node(t);
            newRoot.leaf=false;
            newRoot.insertChild(left,0);
            this.root=newRoot;
            parent=newRoot;
        }
        //1.创建right节点，把left中t以及t以后的key和child移动过去
        Node right=new Node(t);
        right.leaf=left.leaf;//新的节点与老节点同一级
        System.arraycopy(left.keys,t,right.keys,0,t-1);
        //如果left节点不是叶子节点
        if(!left.leaf){
            System.arraycopy(left.children,t,right.keys,0,t);
        }
        right.keyNumber=t-1;
        left.keyNumber=t-1;
        //2.将中间的key（t-1)插入到父节点
        int mid=left.keys[t-1];
        parent.insertKey(mid,inxdex);
        //3.right节点作为父节点子孩子
        parent.insertChild(right,inxdex+1);
    }
}
